package com.mathstruct;

public class Fig02_09 {

    public static final int NOT_FOUND = -1;

    /**
     * Performs the standard binary search.
     *
     * @return index where item is found, or -1 if not found
     */
    public static <AnyType extends Comparable<? super AnyType>> int binarySearch(
            AnyType[] a, AnyType x) {
        int low = 0, high = a.length - 1;

        while (low <= high) {
            int mid = (low + high) / 2;

            if (a[mid].compareTo(x) < 0) {
                low = mid + 1;
            } else if (a[mid].compareTo(x) > 0) {
                high = mid - 1;
            } else {
                return mid; // Found
            }
        }
        return NOT_FOUND; // NOT_FOUND is defined as -1
    }

    // Test program
    public static void main(String[] args) {
        int SIZE = 8;
        Integer[] a = new Integer[SIZE];
        for (int i = 0; i < SIZE; i++) {
            a[i] = i * 2;
        }

        for (int i = 0; i < SIZE * 2; i++) {
            System.out.println("Found " + i + " at " + binarySearch(a, i));
        }
    }
}
